class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    def inorderSuccessor(self, root, p):
        """
        :type root: TreeNode
        :type p: TreeNode
        :rtype: TreeNode
        """
        while root:
            if root.val < p.val:
                root = root.right
            else:
                break
        if root.val == p.val:
            node = root.right
            if not node:
                return None
            else:
                while node.left:
                    node = node.left
                return node
        else:
            stack = [root]
            stack.append(root.left)
            node = stack[-1]
            while node.val != p.val:
                if node.val > p.val:
                    stack.append(node.left)
                    node = stack[-1]
                else:
                    stack.append(node.right)
                    node = stack[-1]
            if node.right:
                node = node.right
                while node.left:
                    node = node.left
                return node
            else:
                while stack[-1].val <= p.val:
                    stack.pop()
                return stack[-1]


